| class A_PQ{T < $IS_LT{T}} < $PQ{T} |
|---|
| **** |
__E_is_the_element_type._ __W_is_the_weight_type Priority queue implemented using an array based heap. Retrieves maximal elements first. _ Usage: ____a:_PQ{INT}_:=_#(#ARRAY{INT}(|2,3,4,5|)); ____#OUT+a.pop+","+a.pop+","+a.pop;_--_prints_5,4,3 ____wrap:_PQMIN{INT};_--_Used_as_a_class_alias_for_the_create_below ____a:_PQ{PQMIN{INT}}:=#(|wrap.create(2),wrap.create(4),wrap.create(3)|); ____#OUT+a.pop+","+a.pop+","+a.pop;_--_prints_1,3,4 ____wrap:_PQWT{STR,INT}; ____a:_PQ{PQWT{STR,INT}}:=#(wrap.create("a",1),wrap.create("b",2)|); ____#OUT+a.pop+","+a.pop+","+a.pop;_--_prints_"(b,2)_(a,1)" _ Design note: It is better to provide access to weight changing methods via an auxilliary wrapper, since that permits external objects to change the weight without searching through all elements |
| $PQ{_} | $DISPENSER{_} | $STR | $CONTAINER{_} | $ELT{_} | $ELT | COMPARE{_} |
| attr size:INT; |
|---|
| **** | Bottom of queue, = number of elements. |
| bounded_insert(e: T, bnd: INT) |
|---|
| **** | Insert "e", then keep popping until there are fewer than "bnd" elements left |
| check_heap:BOOL |
|---|
| **** | True if `self' is a legal heap. |
| clear |
|---|
| **** | Clear the queue. |
| copy: SAME |
|---|
| create(a: $ELT{T}): SAME |
|---|
| **** | Return a new priority queue constructed out of the elements of "a" |
| create:SAME |
|---|
| **** | A new empty priority queue. |
| create_from(a: ARRAY{T}): SAME |
|---|
| **** | Permits use of the literal syntax using type inference |
| create_sized(n:INT):SAME |
|---|
| **** | A new empty priority queue, initially sized to hold `n' elements. |
| current: T |
|---|
| delete(e:T): T |
|---|
| **** | removes e from the heap if it is present and returns it otherwise returns void |
| elt_str(e: T): STR |
|---|
| has(e: T): BOOL |
|---|
| **** | Whether the queue has "e" |
| insert(e:T) |
|---|
| **** | Insert `e' into priority queue. i.e. insert location(size+1) >= size of array(arr.asize-1) Since we start off with an array of size 0, need to add 2 below |
| insert(e: T): SAME |
|---|
| is_empty:BOOL |
|---|
| **** | True if queue is empty. |
| pop:T |
|---|
| **** | Pops off the first element or `void' if empty. |
| remove: T |
|---|
| str: STR |
|---|
| **** | Prints out a string version of the flist of the components that are under $STR |
| top:T |
|---|
| **** | Top element or `void' if empty. |
| elt!: T |
|---|
| **** | NOTE: In any order, NOT in priority order! That would be much more expensive, and is probably best done by popping elemetns off and then putting them in another queue. |
| pop!: T |
|---|
| **** | Yield the elemnts of the queue in priority order, emptying the queue |
| attr arr:ARRAY{T}; |
|---|
| **** |
| attr arr:ARRAY{T}; |
|---|
| **** |
| elt_eq(e1,e2:ETP):BOOL .. Included as elt_eq |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_hash(e:ETP):INT .. Included as elt_hash |
|---|
| **** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
| elt_lt(e1,e2:ETP):BOOL .. Included as elt_lt |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_nil: ETP .. Included as elt_nil |
|---|
| **** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
| is_elt_nil(e:ETP):BOOL .. Included as is_elt_nil |
|---|
| sift_dn(l,u:INT) |
|---|
| **** | Make an `l,u' heap from an `l+1,u' heap in area. |
| sift_up(l,u:INT) |
|---|
| **** | Makes an `l,u' heap from a `l,u-1' heap in area. |
| attr size:INT; |
|---|
| **** | Bottom of queue, = number of elements. |